package com.lfg.leetcode.leetcode200;


public class No287findDuplicate {


    public static void main(String[] args) {
        System.out.println(findDuplicate(new int[]{3, 1, 3, 4, 2}));
    }

    public static int findDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (i == num - 1) {
                continue;
            }
            if (nums[num - 1] == num) {
                return num;
            }
            swap(nums, i, num - 1);
            i--;
        }
        return 0;
    }

    public static void swap(int[] num, int i, int j) {
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }
}

